package 递归回溯;

import java.util.ArrayList;
import java.util.List;

public class JZ16数值的整数次方 {

    /**
     * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
     *
     * 示例 1：
     * 输入：x = 2.00000, n = 10
     * 输出：1024.00000
     * 示例 2：
     * 输入：x = 2.10000, n = 3
     * 输出：9.26100
     * 示例 3：
     * 输入：x = 2.00000, n = -2
     * 输出：0.25000
     * 解释：2-2 = 1/22 = 1/4 = 0.25
     *  
     * 提示：
     * -100.0 < x < 100.0
     * -231 <= n <= 231-1
     * -104 <= xn <= 104
     */

    private List<Double> list=new ArrayList<>();

    //x的n次幂
    public double myPow(double x, int n) {
        if(n==0){
            return 1;
        }
        boolean isFushu=false;
        if(n==Integer.MIN_VALUE){
            n=Integer.MAX_VALUE-1;//瑕疵,因为MIN是偶数,MAX是奇数
            isFushu=true;
        }
        if(n<0){
            n=-n;
            isFushu=true;
        }
        dg(x,n);
        double sum=1;
        for (Double dou : list) {
            sum*=dou;
        }
        if(!isFushu) {
            return sum;
        }else{
            return (double)1/sum;
        }
    }

    //n次幂
    private void dg(double x, int n) {
        if(n<=0){
            return;
        }
        if(n==1){
            list.add(x);
            return;
        }
        if(n%2!=0){
            list.add(x);
        }
        //不管如何
        dg(x*x,n/2);
    }

    public static void main(String[] args) {
        JZ16数值的整数次方 jz=new JZ16数值的整数次方();
        double result = jz.myPow(-1.00000,-2147483648);//x的n次幂
        System.out.println(result);
    }

}
